There are different routing protocols used by network operators to route traffic data in a communications network. Many network operators use, for example, the interior gateway protocol (IGP) network routing protocols.
IGPs are a family of related protocols which have been in existence for some time, and are widely deployed.
The family of IGPs includes different protocols, such as the Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).
In some IGPs the default routing strategy is shortest path first (SPF) routing. Some IGPs allow link metrics to be assigned by the operator to each link in the network. In these cases, a path is the shortest path in the sense that the sum of link metrics along the path is minimal amongst all possible paths. In other IGPs, the shortest path is simply the path with the lowest hop count (i.e. the path with the shortest number of links). In all cases, IGPs use distributed protocols so that, once the protocols are in a converged state, all nodes in the network have the same view of the shortest path between a given source and destination node pair.
An alternative to IGPs is explicit-path protocols. Recently, the multi-protocol label-switching traffic engineering MPLS-TE protocol has been developed as an alternative routing protocol. This is an example of an explicit-path protocol. However, the MPLS-TE is (as yet) much less widely used than the IGPs.
The method of routing traffic using explicit-path protocols is considerably different from IGPs. The network operator may specify explicit paths on the network. These paths carry the data traffic all the way from its source node to its destination node. In MPLS-TE, explicit paths may be established by first informing the source node which destination node is required, and of certain other required parameter settings relating to the request. Then, sufficient details are communicated to all the nodes along the explicit path, so that these nodes can recognise packets on the paths and so that they know where to forward such packets.
When a data packet enters the network at the source node, the node selects for the packet one of the paths which starts at the source node and finishes at the destination node. The packet is then routed along the first link in this path. When the packet arrives at a subsequent, intermediate path node before the destination, this intermediate node determines which path the packet is in. At such a node, the packet is then forwarded along the next explicitly defined link in its path.
In a first scenario where a network operator wishes to migrate from one routing protocol to another, the network operator may want to migrate incrementally. For example, in migrating from an IGP routing protocol such as OSPF to the MPLS-TE protocol, a step-by-step approach is usually desired by network operators. This is due to the concern that an immediate switch to the new protocol may cause unpredicted disruption to the traffic on their network, and other unpredicted operational problems.
In addition to the migration scenario, a second scenario that causes difficulties for the network operators is when they wish to apply a routing protocol for the purposes of data collection, as some routing protocols have superior data collection characteristics to others.
As an example, network operators may wish to deploy MPLS TE for the purposes of gathering traffic matrix information about the size of the traffic between source-destination node pairs, while adhering to the IGP routing currently implemented on their network. This traffic matrix information may be used to improve the IGP routing metrics, or may be used as input to other network configuration or capacity planning decisions, or to assist in implementing an incremental migration strategy.
To clarify this point further, IGP metrics, or alternatively MPLS-TE paths, need to be calculated so as to avoid congestion. However this calculation depends on accurate end-to-end traffic matrix estimates. These estimates depend in turn on measurements that indicate how much traffic is passing between each pair of source and destination nodes. In this way the network operator can establish the effects of changing IGP link metrics, or of MPLS-TE paths for certain source-destination node pairs on various routes, and can thus evaluate whether the network is susceptible to congestion. Installing IGP metrics or MPLS-TE paths without knowledge of the traffic matrix carries a high risk that congestion occurs in the network. If the network operator does not know the amount of traffic between the source and the destination nodes, he or she cannot predict congestion.
Once MPLS-TE paths are in place, it is usually possible to query each path to give an accurate measurement of the traffic flow over that path. However, nodes running IGP protocols do not provide this end-to-end traffic matrix information. In order to collect an accurate end-to-end traffic matrix from an IGP network in the absence of MPLS TE, resource-consuming methods need to be employed, such as the installation of costly hardware probes in the network or the installation of possibly disruptive analysis software.
Returning to the first migration scenario, in migrating IGPs to MPLS-TE protocols, the network operator experiences a major difficulty unless a data collection process is implemented. This is because MPLS-TE paths that differ from the current routing cannot be calculated and safely installed without a traffic matrix, and the traffic matrix cannot be cheaply and accurately measured unless MPLS-TE paths are installed.
A third scenario is when network operators wish deploy an alternative protocol due to its superior characteristics under network failure situations. As an example, network operators implementing IGP routing may wish to deploy MPLS TE because of its bandwidth protection capabilities which have a high restoration speed, and can guarantee to protect quality of service temporarily after network link or node failures. However, they may wish to achieve this without affecting the network operation under normal conditions.
One aim of the present invention is therefore to alleviate the difficulties of a migration between two different routing protocols.
Another aim of the present invention is to determine traffic paths in a communications network that mimic the routing behaviour under an existing or previously implemented routing protocol, whilst taking into account constraints imposed by another routing protocol.
Another aim of the present invention is to facilitate the extraction of traffic flow data from a communications network
Another aim of the present invention is to facilitate the provision of back-up facilities for operating a communications network
According to one aspect of the present invention, there is provided a method of determining traffic paths between one or more source-destination node pairs in a communications network, comprising starting from a first set of paths between said source-destination node pairs, determining a second set of paths between said source-destination node pairs while taking into account a set of constraints, such that said second set of paths emulates said first set of paths.
According to another aspect of the present invention, there is provided a method of calculating traffic paths between one or more source-destination node pairs in a communications network, comprising starting from a first set of paths between said source-destination node pairs, determining a second set of paths between said source-destination node pairs while taking into account a set of constraints, such that said second set of paths is similar to the first set of paths; and the traffic load of said second set of paths is similar to the traffic load of said first set of paths.
According to another aspect of the present invention, there is provided a method of calculating traffic paths between one or more source-destination node pairs in a communications network, comprising starting from a first set of paths between said source-destination node pairs determined using a first routing protocol, determining a second set of paths between said source-destination node pairs for use with a second routing protocol, such that the load balancing in said first and second routing protocols is similar.
FIG. 1 illustrates a simplified example of a communications network. Generally, such a network consists of nodes 2 and links 4. Links 4 carry data traffic between nodes 2. Here, link refers to the capability, as provided by various combination of equipment, to send traffic in one direction between two nodes. Traffic, usually in the form of data packets, enters the network at a source 6 node, is carried over the network via various links and nodes, and finally leaves the network at a destination node 8.
Network links have a numeric capacity indicating the magnitude of traffic they can carry. By altering their configuration, the nodes and links can be made to route traffic in different ways, i.e. to route traffic along different alternative path combinations. Network Quality of Service (QoS) is an important consideration when choosing the routing. If at any stage a link has more traffic on it than its capacity, it is said to be congested. Congested links lead to degraded quality of service. Therefore, network operators strive to configure the routing of their traffic carefully and try to avoid congestion. Other considerations regarding QoS are taken into account. They include path delay, that is, the length of time it takes for the traffic to travel from the source node to the destination node, and other QoS requirements such as jitter. In the following, congestion has been used to illustrate QoS requirements, without loss of generality, and as an example only of the various QoS requirements.
Network routing is done via a routing protocol as described above. The communications network 1 may be connected to other networks 10.
FIG. 2 illustrates the relationship of the network and a network management system 60 in which the present invention may be implemented. Network management system 60 performs the network management functions for network 50. The network management system communicates with the network using a network management protocol, such as the Simple Network Management Protocol (SNMP). The network management system 60 includes a processor 62 and a memory 64 and may comprise a commercially available server computer. A computer program performing the calculation of data traffic is stored is memory 64 and can be executed by processor 62.